以 CF1327F 为代表的一类限制计数问题
这类有限制的计数问题，套路在状态设计上。一般是区间上的问题，切入点是发现 dp 的要点有当前位置和满足限制的位置以及满足了哪些限制；转移就是 对于同一种限制同一个右端点找到最大的左端点，这之间必须有一个满足要求的位置。
$CF1327F$
按位处理，可以算出每一位的答案然后乘起来。子问题的解决必须是 $O(n)$ 的！！
限制为 1 很好处理，全部强制为 1 就可以了；为 0 就比较难搞，要求至少有一个位置是 0。
先只考虑为 0 的限制。对于一个位置 $i$ 找到所有右端点 $\leq i$ 的限制的最大左端点，设其为 $l_i$。$f[i, j]$ 表示填完了前 $i$ 个位置，满足了右端点 $\leq i$ 的所有限制，最后一个 0 的位置在 $j$，其中 $l_i \leq j \leq i$ 的方案数
那么 $f[i, j] = f[i - 1, j]$ $(j < i)$，$f[i, i] = \sum\limits_{k = l_{i - 1}}^{i - 1} f[i - 1, k]$
想优化空间。发现 $i \neq j$ 的 $f[i, j]$ 好像没什么用，干脆令 $f[i]$ 表示原来的 $f[i, i]$，$f[i] = \sum\limits_{k = l_{i - 1}}^{i - 1} f[k]$。发现求了一个后缀和，又发现 $l_i$ 单调递增，所以 dp 是 $O(n)$ 的。
那加上 1 的限制怎么办？把那些已经强制为 1 的点拎走，剩下的做 dp。
$[清华集训2017]-某个歌姬的故事$
离散化（u1s1这题离散化是大毒瘤。）
预处理出每个位置的上限 $up_i$，这样就把 $up_i$ 相同的相邻位置缩成了一个点。
对于限制 $[l_j, r_j, m_j]$ 显然只有 $l_j \leq i \leq r_j$ 中 $up_i = m_j$ 的点能贡献。
于是对于每个 $m_j$ 将所有 $up_i = m_j$ 的点拿出来做 dp。
怎么d？显然是满足每个限制区间内有一个点达到上限即可。
令 $f[i, j]$ 表示满足所有 右端点在 $1$ ~ $i$ 的限制，选的最后一个点是 $j$ 的方案数。
不同的 $m_j$ 是独立的，分别 dp 后把答案乘起来。
$[NOI2020 D1T2]-命运$
区 间 上 树（
这个比赛时连 dp 方程都想不到。。。就写了最暴力的指数级容斥。。但实际上跟前两题的 dp 设计思路是很相似的！
$dp[i, j]$ 表示 $i$ 的子树内状态已经确定，没有满足的链顶点的最大深度为 $j$ 的方案数（记录最深是因为深的满足了，浅的也满足了），边界就是链都满足了，$j = 0$
前两部分分别是 $(x, y)$ 这条边为 1 和为 0 的方案数。
二维dp，前缀和形式。。噫，这个东西和 pkuwc2018-minimax 好像啊！没错，就是整体dp，上线段树合并。
跟 minimax 一样的，碰到叶子结点就返回，其他节点由儿子节点 upd 上来。